package 算法.NiuKe.JZ;


import 算法.NiuKe.TreeLinkNode;

/**
 * @author:谢君臣
 * @Date:2021/4/2616:59
 * @version:1.0
 * @function:   给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
 *              注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。
 */
public class JZ58 {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode==null)
            return null;
        if (pNode.right!=null) { //右节点不为空
            TreeLinkNode node = pNode.right;
            while (node.left!=null)node = node.left;
            return node;
        }else {
            if (pNode.next==null)
                return null;
            else if (pNode.next.left == pNode )return pNode.next;
            else{
                TreeLinkNode node = pNode;
                while (node!=null){
                    if (node.next!=null&&node.next.right==node)
                        node = node.next;
                    else break;
                }
                return node.next;
            }
        }
    }
}

